The Fibonacci Sequence

$F(1) = 0$

$F(2) = 1$

$F(N) = F(N-1) + F(N-2)\;\;\;\;\;\ $ (for $N > 2$)

The Fibonacci Spiral

• An approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling

We can see this in the sunflower, for example:

def fib(n: int) -> int:
        if n == 1:
            return(1)
        elif n == 0:
            return(0)
        else:
            return(fib(n-1)+fib(n-2))

fib(6)

https://www.mathsisfun.com/games/towerofhanoi.html

• Also called the Tower of Brahma

• The Towers of Hanoi actually have very little to do with the city of Hanoi in present day Vietnam.

• The earliest recorded reference is from Édouard Lucas (in Récréations Mathématiques, Vol. 3, pp. 55–59, Gauthier-Villars, Paris, 1893)..

  • ..who reports that there is in the temple of Kashi Vishwanath in Varanasi, Uttar Pradesh, India, a set of 64 gold disks on 3 diamond needles called the Tower of Brahma which monks have been trying to solve since the beginning of time.

Home work! :-P

• Write a recursive programme to solve the Tower of Brahma.

• Write an iterative programme to solve the Tower of Brahma.

Tower of Brahma - 1 Disc

Solution

1. tbrahma(1,s,i,d)
   • Move Disc from Source to Destination

Tower of Brahma - 2 Discs

Solution

1. Move Disc 1 from Source to Intermediate
2. Move Disc 2 from Source to Destination
3. Move Disc 1 from Intermediate to Destination

Tower of Brahma - 2 Discs

Solution

1. Move Disc 1 from Source to Intermediate
2. Move Disc 2 from Source to Destination
3. Move Disc 1 from Intermediate to Destination

Write this in terms of the base case (1 Disc)

Tower of Brahma - 2 Discs

Write this in terms of the base case (1 Disc)

1. Call Disc 1 solution for the first disc with Intermediate and Destination interchanged
   • tbrahma(1,s,d,i)
2. Call Disc 1 solution for the second disc
   • tbrahma(2,s,i,d)
3. Call Disc 1 solution for the first disc
   • tbrahma(1,i,s,d)

Tower of Brahma

Tower of Brahma

Solution

1. Move 2 discs from Source to Intermediate
2. Move Disc 3 from Source to Destination
3. Move 2 discs from Intermediate to Destination

Why recursion?

• Recursive thinking is important in programming

  • It helps break down big problems into smaller ones
  • Let's the machine do all the work! :-)

• Sometimes, it is easier to understand the recursive solution to a problem compared to the iterative one.

• At times, the recursive implementation may not be as efficient as the iterative one.

def ifact(n):
    assert n >= 0 and int(n) == n, 'positive integers only!'
    ans = 1
    for i in range(n):
        ans = ans * (i+1)
    return(ans)

def rfact(n):
    assert n >= 0 and int(n) == n, 'positive integers only!'
    if n == 0 or n == 1:
        return 1
    return(n * rfact(n-1))

%timeit ifact(2500)
%timeit rfact(2500)

# compute y = $x^n$ using iteration

def iexp(x,n):
    assert n >= 0 and int(n) == n, 'bad input'
    y = 1 
    if n == 0:
        return 1
    for i in range(n):
        #print(i+1)
        y = y*x
    return(y)
    

# compute y = $x^n$ using recursion

def r2exp(x,n):
    assert n >= 0 and int(n) == n, 'n must be a positive integer'
    if n == 0:
        return 1
    #print(x,n)
    result = r2exp(x*x,n//2)
    if n % 2 == 0:
        return(result)
    else:
        return(x*result)

# compute y = $x^n$ using recursion

def r3exp(x,n):
    assert n >= 0 and int(n) == n, 'n must be a positive integer'
    if n == 0:
        return 1
    if n == 1:
        return (x)
    if n == 2:
        return(x*x)
    #print(x,n)
    result = r3exp(x*x*x,n//3)
    rem = n % 3 
    if rem == 0:
        return(result)
    elif rem == 1:
        return(x*result)
    else:
        return(x*x*result)

iexp(3,4)
rexp(3,4)

---